package fly.leetcode.cn.q1025;

import java.util.BitSet;

/**

 * 限制： 1 <= N <= 1000
 * 分析： 1. 本质，判断这是不是一个先手必胜的游戏，如果这个游戏状态是先手必胜（true），那必然是后手必输（false）
 *       2. 如果爱丽丝先手，那判断可不可以通过一个回合把游戏变成后手必输的状态
 *       3. (可以读取以前的缓存的情况下)先缓存所有后手必输的游戏状态n，随后拿到N后遍历判断 N % n == 0 ( 1<= n <= N/2 )，如果等式成立，则可以通过选择N-n把游戏变成后手必输
 *       4. (不能读取缓存的情况下)便利所有可能选择的n( 1<= n <= N/2 )，判断 N % n == 0 && F(N-n) == false，则可以通过选择N-n把游戏变成后手必输)
 *
 */

class Solution3 extends Solution {

    public static final BitSet bitset = BitSet.valueOf(new long[]{6148914691236517204L, 6148914691236517205L, 6148914691236517205L, 6148914691236517205L,
            6148914691236517205L, 6148914691236517205L, 6148914691236517205L, 6148914691236517205L,
            6148914691236517205L, 6148914691236517205L, 6148914691236517205L, 6148914691236517205L,
            6148914691236517205L, 6148914691236517205L, 6148914691236517205L, 1466015503701L});

    @Override
    public boolean divisorGame(int N) {
        return bitset.get(N);
    }
}
